home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / incl / LEDA.020+881 / impl / slist.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  4.0 KB  |  164 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  slist.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_IMPL_SLIST_H
  17. #define LEDA_IMPL_SLIST_H
  18.  
  19. //------------------------------------------------------------------------------
  20. // simply linked lists
  21. //------------------------------------------------------------------------------
  22.  
  23.  
  24. #include <LEDA/basic.h>
  25.  
  26.  
  27. class SLIST; 
  28. class slink;
  29.  
  30. typedef slink* slist_item;
  31.  
  32. //------------------------------------------------------------------------------
  33. // class slink 
  34. //------------------------------------------------------------------------------
  35.  
  36. class slink {
  37.  
  38.   friend class SLIST;
  39.  
  40.   slink* succ;
  41.   GenPtr e;
  42.  
  43.   slink(GenPtr a, slink* suc) { e = a; succ = suc; }
  44.  
  45.   LEDA_MEMORY(slink)
  46.  
  47. };
  48.  
  49.  
  50. //------------------------------------------------------------------------------
  51. // SLIST: base class for all simply linked Lists
  52. //------------------------------------------------------------------------------
  53.  
  54. class SLIST {
  55.  
  56.    slink* h;                     //head
  57.    slink* t;                     //tail
  58.    slink* iterator;              //iterator;
  59.    int    count;                 //length of List
  60.  
  61. virtual void clear_el(GenPtr&) const {}
  62. virtual void copy_el(GenPtr&)  const {}
  63. virtual int  int_type() const { return 0; }
  64.  
  65. public:
  66.  
  67.    int space()  const { return sizeof(SLIST) + count * sizeof(slink); }
  68.    int length() const { return count; }
  69.    int empty()  const { return (count==0);}
  70.  
  71.    slink* insert(GenPtr, slink*);
  72.  
  73.  
  74.    slink* push(GenPtr a)   
  75.    { count++;
  76.      h = new slink(a,h); 
  77.      if (t==0) t = h;
  78.      return h;
  79.    }
  80.  
  81.    slink* append(GenPtr a)
  82.    { count++;
  83.      if (t) t = t->succ = new slink(a,0); 
  84.      else   t = h = new slink(a,0); 
  85.      return t;
  86.    } 
  87.  
  88.    slink* first()               const { return h; }
  89.    slink* first_item()          const { return h; }
  90.    slink* last()                const { return t; }
  91.    slink* last_item()           const { return t; }
  92.    slink* next_item(slink* p)   const { return p->succ; }
  93.    slink* succ(slink* l)        const { return l->succ; }
  94.    slink* cyclic_succ(slink*)   const;
  95.  
  96.  
  97. // iteration
  98.  
  99.    void   set_iterator(slink* p)   const { (slink*&)iterator = p; }
  100.    void   start_iteration()        const { set_iterator(h); }
  101.    void   move_to_succ()           const { set_iterator(iterator->succ); }
  102.    slink* read_iterator(GenPtr& x) const { if (iterator) x = iterator->e; 
  103.                                            return iterator; }
  104.  
  105.    GenPtr loop_to_succ(GenPtr& x) const { return x = slist_item(x)->succ; }
  106.  
  107. // old iteration stuff
  108.  
  109.    slink* get_iterator()  const { return iterator; }
  110.    void init_iterator()  const { set_iterator(0); }
  111.  
  112.    slink* move_iterator() const  
  113.    { set_iterator( iterator ? iterator->succ : h);
  114.      return iterator;
  115.    } 
  116.  
  117.    void conc(SLIST&);
  118.  
  119.    GenPtr head()   const { return h ? h->e : 0;}
  120.    GenPtr tail()   const { return t ? t->e : 0;}
  121.    GenPtr pop();
  122.  
  123.    void del_succ(slink* p)    
  124.    { slink* q = p->succ;
  125.      if (q == t) t = p;
  126.      p->succ = q->succ; 
  127.      delete q;
  128.      count--;
  129.    }
  130.  
  131.    bool current_element(GenPtr& x)  const
  132.    { if (!iterator) return false;
  133.      else { x = iterator->e;
  134.             return true; }
  135.     }
  136.  
  137.    bool next_element(GenPtr& x) const 
  138.   { move_iterator(); 
  139.     return current_element(x); 
  140.    }
  141.  
  142.    GenPtr  contents(slink* l)  const  { return l->e; }
  143.    GenPtr& entry(slink* l)            { return l->e; }
  144.    GenPtr& operator[](slink* l)       { return l->e; }
  145.    GenPtr  operator[](slink* l) const { return l->e; }
  146.  
  147.    void clear();
  148.  
  149.    SLIST();    
  150.    SLIST(GenPtr a);
  151.    SLIST& operator=(const SLIST&); 
  152.    SLIST(const SLIST&);
  153.    virtual ~SLIST()     { clear(); }
  154. };
  155.  
  156.  
  157. // dummy I/O and cmp functions
  158.  
  159. inline void Print(const SLIST&,ostream&) { }
  160. inline void Read(SLIST&, istream&) { }
  161. inline int  compare(const SLIST&,const SLIST&) { return 0; }
  162.  
  163. #endif
  164.